package ljl.alg.wangzheng_camp.round1.backtrack;

import java.util.Arrays;

public class _494_target_sum {
    
    /**
     * 我第一反应这个题就是在考 backtrack
     *
     * 回溯非常优雅，代码也很简单
     * 就是特别慢，耗时 500ms
     * 这个一般就去等消息了？也不一定
     *
     * */
    static class backtrack {
        int count;
        public int findTargetSumWays(int[] nums, int target) {
            track(nums, 0, target, 0);
            return count;
        }
        void track(int[] nums, int i, int t, int cur) {
            if (i == nums.length) {
                if (t == cur)
                    count++;
                return;
            }
            track(nums, i + 1, t, cur + nums[i]);
            track(nums, i + 1, t, cur - nums[i]);
        }
    }
    
    /**
     * dp 需要更多思考..
     *
     * 都是正数对吧？有些数字需要加上 -，设它们和为 neg
     * 然后正数之和减去负数之和为 target，故
     * sum - neg - neg = sum - 2 * neg = target
     *
     * 开启第一发验证 net = (sum - target) / 2 必须是整数，否则直接返回 0，很不错
     *
     * 然后这个 neg 是重点，dp 解法就围绕着它转了
     * 设数组 dp[i][j]，含义是从前 i 个元素里选择，能凑出来 j 的方案个数
     * dp[0][0] = 1，不选，凑成 0，方案数是 1 个
     * 然后递推公式，对于每个数 num：
     *  dp[i][j] =
     *      if j < num: dp[i - 1][j]
     *          意思是如果 j 比 num 还小，那只能和上一把和为 j 的一样了
     *      else: dp[i - 1][j] + dp[i - 1][j - num]
     *          如果 j 比较大，num 可选可不选，就是两种情况的和
     * */
    static class dp {
        public int findTargetSumWays(int[] nums, int target) {
            int sum = Arrays.stream(nums).sum();
            if ((sum - target) % 2 != 0) return 0;
            int neg = (sum - target) / 2;
            if (neg < 0) return 0;
            int n = nums.length;
            int[][] dp = new int[n + 1][neg + 1];
            dp[0][0] = 1;
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j <= neg; j++) {
                    dp[i][j] = dp[i - 1][j];
                    if (j >= nums[i - 1])
                        dp[i][j] += dp[i - 1][j - nums[i - 1]];
                }
            }
            return dp[n][neg];
        }
        
        /**
         * 和上面一样，使用一维数组优化空间复杂度
         * */
        public int findTargetSumWays2(int[] nums, int target) {
            int sum = Arrays.stream(nums).sum();
            if ((sum - target) % 2 != 0) return 0;
            int neg = (sum - target) / 2;
            if (neg < 0) return 0;
            int[] dp = new int[neg + 1];
            dp[0] = 1;
            for (int num : nums) {
                for (int j = neg; j >= num; j--) {
                    dp[j] += dp[j - num];
                }
            }
            return dp[neg];
        }
    }
    
}
